`
https://leetcode.cn/problems/find-in-mountain-array/
`

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * function MountainArray() {
 *     @param {number} index
 *     @return {number}
 *     this.get = function(index) {
 *         ...
 *     };
 *
 *     @return {number}
 *     this.length = function() {
 *         ...
 *     };
 * };
 */

/**
 * @param {number} target
 * @param {MountainArray} mountainArr
 * @return {number}
 */
var findInMountainArray = function (target, mountainArr) {
  const n = mountainArr.length()
  // 拿到山峰下标
  const highest = findHighest(mountainArr)

  // 在上坡查找
  let left = -1, right = highest + 1
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    const val = mountainArr.get(mid)
    if (val === target) return mid
    if (val < target) {
      left = mid
    } else {
      right = mid
    }
  }

  // 在下坡查找
  let lo = highest, hi = n
  while (lo + 1 < hi) {
    const mid = lo + Math.floor((hi - lo) / 2)
    const val = mountainArr.get(mid)
    if (val === target) return mid
    if (val < target) {
      hi = mid
    } else {
      lo = mid
    }
  }
  // 没找到
  return -1
};

function findHighest(arr) {
  const n = arr.length()

  let left = -1, right = n
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    const val = arr.get(mid)
    const nextVal = arr.get(mid + 1)
    if (val > nextVal) {
      // 在峰顶或下坡
      right = mid
    } else {
      left = mid
    }
  }
  return right
}